#include <iostream>
#include <cstdio>

#define N 10000007

using namespace std;

int memo[N];
int modn;

int f(int i){
    if(memo[i]) return memo[i];
    if(i == 1 || i == 2){
        return memo[i] = i % modn;
    }
    else return memo[i] = (f(i - 1) + f(i - 2)) % modn;
}

int main(){
    cin >> modn;
    int x = 1;
    while(f(x) != 0 || f(x + 1) != 1){
        ++x;
    }
    cout << x+1;
    return 0;
}